<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>搜索旋转排序数组 - 算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-text {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 12px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        .code-dots {
            display: flex;
            gap: 8px;
        }
        .dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        .dot-red { background: #ff5f56; }
        .dot-yellow { background: #ffbd2e; }
        .dot-green { background: #27c93f; }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            font-size: 14px;
            line-height: 1.6;
            color: #d4d4d4;
        }
        .keyword { color: #c586c0; }
        .type { color: #4ec9b0; }
        .function { color: #dcdcaa; }
        .string { color: #ce9178; }
        .comment { color: #6a9955; }
        .number { color: #b5cea8; }
        .operator { color: #d4d4d4; }
        .first-letter {
            float: left;
            font-size: 4rem;
            line-height: 3rem;
            padding-right: 8px;
            margin-top: 4px;
            font-weight: 700;
            color: #667eea;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        .complexity-badge {
            display: inline-flex;
            align-items: center;
            padding: 6px 16px;
            background: rgba(102, 126, 234, 0.1);
            border: 1px solid rgba(102, 126, 234, 0.3);
            border-radius: 20px;
            font-size: 14px;
            color: #667eea;
            font-weight: 500;
        }
        .step-indicator {
            width: 40px;
            height: 40px;
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            border-radius: 50%;
            display: flex;
            align-items: center;
            justify-content: center;
            color: white;
            font-weight: bold;
            flex-shrink: 0;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-4xl mx-auto text-center">
            <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">搜索旋转排序数组</h1>
            <p class="text-xl md:text-2xl opacity-90 mb-8">掌握二分查找的高级应用，优雅解决旋转数组问题</p>
            <div class="flex justify-center gap-4 flex-wrap">
                <span class="complexity-badge bg-white bg-opacity-20 border-white border-opacity-30 text-white">
                    <i class="fas fa-clock mr-2"></i>时间复杂度 O(log n)
                </span>
                <span class="complexity-badge bg-white bg-opacity-20 border-white border-opacity-30 text-white">
                    <i class="fas fa-memory mr-2"></i>空间复杂度 O(1)
                </span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-puzzle-piece mr-3 gradient-text"></i>
                    <span class="gradient-text">问题描述</span>
                </h2>
                <div class="prose prose-lg max-w-none">
                    <p class="text-gray-700 leading-relaxed">
                        <span class="first-letter serif-font">给</span>定一个升序排列的整数数组 nums，经过某个未知的旋转后，得到一个新的数组。例如，原数组 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2]。给定一个目标值 target，若存在目标值则返回其索引，否则返回 -1。要求时间复杂度为 O(log n)。
                    </p>
                </div>
            </div>
        </section>

        <!-- Algorithm Visualization -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-sitemap mr-3 gradient-text"></i>
                    <span class="gradient-text">算法流程图</span>
                </h2>
                <div class="mermaid">
                    graph TD
                        A[开始] --> B{数组是否为空?}
                        B -->|是| C[返回 -1]
                        B -->|否| D[初始化 left=0, right=n-1]
                        D --> E{left <= right?}
                        E -->|否| C
                        E -->|是| F[计算 mid = left + (right-left)/2]
                        F --> G{nums[mid] == target?}
                        G -->|是| H[返回 mid]
                        G -->|否| I{nums[left] <= nums[mid]?}
                        I -->|是| J[左半部分有序]
                        I -->|否| K[右半部分有序]
                        J --> L{target在左半部分?}
                        L -->|是| M[right = mid - 1]
                        L -->|否| N[left = mid + 1]
                        K --> O{target在右半部分?}
                        O -->|是| P[left = mid + 1]
                        O -->|否| Q[right = mid - 1]
                        M --> E
                        N --> E
                        P --> E
                        Q --> E
                        style A fill:#667eea,stroke:#fff,stroke-width:2px,color:#fff
                        style H fill:#27c93f,stroke:#fff,stroke-width:2px,color:#fff
                        style C fill:#ff5f56,stroke:#fff,stroke-width:2px,color:#fff
                </div>
            </div>
        </section>

        <!-- Solution Steps -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-8 flex items-center">
                    <i class="fas fa-lightbulb mr-3 gradient-text"></i>
                    <span class="gradient-text">解题思路</span>
                </h2>
                <div class="space-y-6">
                    <div class="flex gap-4">
                        <div class="step-indicator">1</div>
                        <div class="flex-1">
                            <h3 class="text-xl font-semibold mb-2">识别有序部分</h3>
                            <p class="text-gray-700">通过比较 nums[left] 和 nums[mid]，判断左半部分还是右半部分是有序的。这是解决旋转数组问题的关键。</p>
                        </div>
                    </div>
                    <div class="flex gap-4">
                        <div class="step-indicator">2</div>
                        <div class="flex-1">
                            <h3 class="text-xl font-semibold mb-2">确定搜索范围</h3>
                            <p class="text-gray-700">根据目标值与有序部分的边界值比较，决定下一步搜索左半部分还是右半部分。</p>
                        </div>
                    </div>
                    <div class="flex gap-4">
                        <div class="step-indicator">3</div>
                        <div class="flex-1">
                            <h3 class="text-xl font-semibold mb-2">二分查找迭代</h3>
                            <p class="text-gray-700">不断缩小搜索范围，直到找到目标值或搜索范围为空。每次迭代都将搜索空间减半，保证 O(log n) 的时间复杂度。</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-lg overflow-hidden card-hover">
                <div class="p-8 pb-0">
                    <h2 class="text-3xl font-bold mb-6 flex items-center">
                        <i class="fas fa-code mr-3 gradient-text"></i>
                        <span class="gradient-text">代码实现</span>
                    </h2>
                </div>
                <div class="code-block mx-8 mb-8">
                    <div class="code-header">
                        <div class="code-dots">
                            <div class="dot dot-red"></div>
                            <div class="dot dot-yellow"></div>
                            <div class="dot dot-green"></div>
                        </div>
                        <span class="text-gray-400 text-sm">Java</span>
                    </div>
                    <pre><code><span class="comment">/**
 * 在旋转排序数组中搜索目标值
 * @param nums 旋转后的排序数组
 * @param target 目标值
 * @return 目标值的索引，若不存在则返回-1
 */</span>
<span class="keyword">public</span> <span class="type">int</span> <span class="function">search</span>(<span class="type">int[]</span> nums, <span class="type">int</span> target) {
    <span class="comment">// 边界检查</span>
    <span class="keyword">if</span> (nums == <span class="keyword">null</span> || nums.length == <span class="number">0</span>) {
        <span class="keyword">return</span> <span class="number">-1</span>;
    }
    
    <span class="comment">// 初始化左右指针</span>
    <span class="type">int</span> left = <span class="number">0</span>;
    <span class="type">int</span> right = nums.length - <span class="number">1</span>;
    
    <span class="comment">// 二分查找</span>
    <span class="keyword">while</span> (left <= right) {
        <span class="comment">// 计算中间位置，避免整数溢出</span>
        <span class="type">int</span> mid = left + (right - left) / <span class="number">2</span>;
        
        <span class="comment">// 如果找到目标值，直接返回索引</span>
        <span class="keyword">if</span> (nums[mid] == target) {
            <span class="keyword">return</span> mid;
        }
        
        <span class="comment">// 判断中间点在哪个部分（左半部分有序还是右半部分有序）</span>
        <span class="keyword">if</span> (nums[left] <= nums[mid]) {
            <span class="comment">// 左半部分有序</span>
            <span class="comment">// 检查目标值是否在左半部分的有序区间内</span>
            <span class="keyword">if</span> (nums[left] <= target && target < nums[mid]) {
                <span class="comment">// 目标在左半部分，缩小搜索范围到左半部分</span>
                right = mid - <span class="number">1</span>;
            } <span class="keyword">else</span> {
                <span class="comment">// 目标在右半部分，缩小搜索范围到右半部分</span>
                left = mid + <span class="number">1</span>;
            }
        } <span class="keyword">else</span> {
            <span class="comment">// 右半部分有序</span>
            <span class="comment">// 检查目标值是否在右半部分的有序区间内</span>
            <span class="keyword">if</span> (nums[mid] < target && target <= nums[right]) {
                <span class="comment">